package phase1.part1;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 
 * 
 * @author John Girata
 * @version Nov 16, 2012
 */
public class RecursiveDescender {
	public enum Result {
		NEW_CHAR_CLASS, NEW_REGEX, FAILURE
	}

	public static final char PRINTABLE_START = 33;
	public static final char PRINTABLE_END = 126;

	private static final Set<Character> RE_SPECIAL;
	private static final Set<Character> CLS_SPECIAL;

	private Result result;
	private Map<String, CharacterClass> classes;
	private int longestClassLength;
	private String lastKey;
	private State lastNFA;
	private CharacterClass lastCC;

	static {
		RE_SPECIAL = new HashSet<>();
		RE_SPECIAL.add('\\');
		RE_SPECIAL.add('*');
		RE_SPECIAL.add('+');
		RE_SPECIAL.add('?');
		RE_SPECIAL.add('|');
		RE_SPECIAL.add('[');
		RE_SPECIAL.add(']');
		RE_SPECIAL.add('(');
		RE_SPECIAL.add(')');
		RE_SPECIAL.add('.');
		RE_SPECIAL.add('\'');
		RE_SPECIAL.add('"');

		CLS_SPECIAL = new HashSet<>();
		CLS_SPECIAL.add('\\');
		CLS_SPECIAL.add('[');
		CLS_SPECIAL.add(']');
		CLS_SPECIAL.add('^');
		CLS_SPECIAL.add('-');
	}

	public RecursiveDescender(Map<String, CharacterClass> classes) {
		this.classes = classes;
		result = Result.FAILURE;
		calcLongestClass();
	}

	private void calcLongestClass() {
		for (String c : classes.keySet()) {
			if (c.length() > longestClassLength) {
				longestClassLength = c.length();
			}
		}
	}

	public RecursiveDescender() {
		this(new HashMap<String, CharacterClass>());
	}

//	public Result process(String text) {
//		StringBuilder key = new StringBuilder();
//
//		if (text.charAt(0) != '$') {
//			return Result.FAILURE;
//		}
//
//		int index;
//
//		for (index = 1; text.charAt(index) >= PRINTABLE_START
//				&& text.charAt(index) <= PRINTABLE_END; index++) {
//			key.append(text.charAt(index));
//		}
//
//		lastKey = key.toString();
//		text = text.substring(index + 1);
//
//		List<Character> chars = new LinkedList<>();
//
//		for (char c : text.toCharArray()) {
//			if (c >= PRINTABLE_START && c <= PRINTABLE_END) {
//				chars.add(c);
//			}
//		}
//
//		CharacterClass cc = charClass(new LinkedList<>(chars));
//		
//		if (cc != null) {
//			classes.put(key.toString(), cc);
//			result = Result.NEW_CHAR_CLASS;
//			lastCC = cc;
//			calcLongestClass();
//			return getResult();
//		}
//		
//		State regex = regEx(new LinkedList<>(chars));
//
//		if (regex != null) {
//			result = Result.NEW_REGEX;
//			lastNFA = regex;
//			return getResult();
//		}
//
//		result = Result.FAILURE;
//		return getResult();
//	}
	
	public Result processCharClass(String text) {
		StringBuilder key = new StringBuilder();

		if (text.charAt(0) != '$') {
			return Result.FAILURE;
		}

		int index;

		for (index = 1; text.charAt(index) >= PRINTABLE_START
				&& text.charAt(index) <= PRINTABLE_END; index++) {
			key.append(text.charAt(index));
		}

		lastKey = key.toString();
		text = text.substring(index + 1);

		List<Character> chars = new LinkedList<>();

		for (char c : text.toCharArray()) {
			if (c >= PRINTABLE_START && c <= PRINTABLE_END) {
				chars.add(c);
			}
		}

		CharacterClass cc = charClass(new LinkedList<>(chars));
		
		if (cc != null) {
			classes.put(key.toString(), cc);
			result = Result.NEW_CHAR_CLASS;
			lastCC = cc;
			calcLongestClass();
			return getResult();
		}
		
		result = Result.FAILURE;
		return getResult();
	}
	
	public Result processRegex(String text) {
		StringBuilder key = new StringBuilder();

		if (text.charAt(0) != '$') {
			return Result.FAILURE;
		}

		int index;

		for (index = 1; text.charAt(index) >= PRINTABLE_START
				&& text.charAt(index) <= PRINTABLE_END; index++) {
			key.append(text.charAt(index));
		}

		lastKey = key.toString();
		text = text.substring(index + 1);

		List<Character> chars = new LinkedList<>();

		for (char c : text.toCharArray()) {
			if (c >= PRINTABLE_START && c <= PRINTABLE_END) {
				chars.add(c);
			}
		}

		State regex = regEx(new LinkedList<>(chars));

		if (regex != null) {
			result = Result.NEW_REGEX;
			lastNFA = regex;
			return getResult();
		}

		result = Result.FAILURE;
		return getResult();
	}

	public Result getResult() {
		return result;
	}

	State regEx(List<Character> text) {
		return rexp(text, new State(true));
	}

	State rexp(List<Character> text, State previous) {
		State first = rexp1(text, new State(true));

		if (first == null || first.getTransitions().isEmpty()) {
			return null;
		}

		State second = rexpPrime(text, previous);

		State firstEnd = findAccepting(first);
		recursivelySetNotAccepting(first);

		State secondEnd = findAccepting(second);
		recursivelySetNotAccepting(second);

		State start = new State();
		start.addTransition(first);
		start.addTransition(second);

		State end = new State(true);
		firstEnd.addTransition(end);
		secondEnd.addTransition(end);

		return start;
	}

	State rexpPrime(List<Character> text, State previous) {
		if (!eat(text, '|')) {
			return new State(true);
		}

		State first = rexp1(text, new State(true));

		if (first.getTransitions().isEmpty()) {
			return new State(true);
		}

		State second = rexpPrime(text, previous);

		if (second.getTransitions().isEmpty()) {
			return first;
		}

		State firstEnd = findAccepting(first);
		recursivelySetNotAccepting(first);

		State secondEnd = findAccepting(second);
		recursivelySetNotAccepting(second);

		State start = new State();
		start.addTransition(first);
		start.addTransition(second);

		State end = new State(true);
		firstEnd.addTransition(end);
		secondEnd.addTransition(end);

		return start;
	}

	State rexp1(List<Character> text, State previous) {
		if (text.isEmpty()) {
			return null;
		}

		State first = rexp2(text, previous);

		if (first.getTransitions().isEmpty()) {
			return new State(true);
		}

		State second = rexp1Prime(text, previous);
		State firstEnd = findAccepting(first);

		if (firstEnd == null) {
			return null;
		}

		recursivelySetNotAccepting(first);
		firstEnd.addTransition(second);

		return first;
	}

	State rexp1Prime(List<Character> text, State previous) {
		if (text.isEmpty()) {
			return new State(true);
		}

		State first = rexp2(text, new State(true));

		if (first.getTransitions().isEmpty()) {
			return new State(true);
		}

		State second = rexp1Prime(text, previous);

		State firstEnd = findAccepting(first);
		recursivelySetNotAccepting(first);
		firstEnd.addTransition(second);

		return first;
	}

	State rexp2(List<Character> text, State previous) {
		State candidate = rexp2a(text, previous);

		if (candidate != null) {
			return candidate;
		}

		candidate = rexp2c(text, previous);

		if (candidate != null) {
			return candidate;
		}

		candidate = rexp2b(text, previous);

		if (candidate != null) {
			return candidate;
		}

		return null;
	}

	State rexp2a(List<Character> text, State previous) {
		List<Character> copy = new LinkedList<>(text);

		if (!eat(copy, '(')) {
			return null;
		}

		State candidate = rexp(copy, new State());

		if (candidate == null) {
			return null;
		}

		if (!eat(copy, ')')) {
			return null;
		}

		candidate = rexp2tail(copy, candidate);

		if (candidate == null) {
			return null;
		}

		text.clear();
		text.addAll(copy);

		return candidate;
	}

	State rexp2b(List<Character> text, State previous) {
		List<Character> copy = new LinkedList<>(text);
		String sequence = eatREChar(copy);

		if (sequence.isEmpty()) {
			return null;
		}

		if (sequence.length() != 1) {
			throw new RuntimeException("Expected sequence to be of length 1");
		}

		State start = new State();
		State end = new State(true);
		start.addTransition(end, sequence);

		State candidate = rexp2tail(copy, start);

		text.clear();
		text.addAll(copy);

		State newPrevious = duplicate(previous);
		State oldEnd = findAccepting(newPrevious);
		recursivelySetNotAccepting(newPrevious);
		// recursivelySetNotAccepting(candidate);
		oldEnd.addTransition(candidate);

		return newPrevious;
	}

	State rexp2c(List<Character> text, State previous) {
		return rexp3(text, previous);
	}

	static String eatREChar(List<Character> text) {
		if (text.size() == 0) {
			return "";
		}

		char candidate = text.get(0);

		// Escape sequence
		if (candidate == '\\') {
			if (text.size() == 1) {
				return "";
			}

			if (RE_SPECIAL.contains(text.get(1))) {
				text.remove(0);
				return "" + text.remove(0);
			}
		}

		// Printable character (less space)
		if (candidate >= PRINTABLE_START && candidate <= PRINTABLE_END) {
			if (RE_SPECIAL.contains(candidate)) {
				return "";
			}

			text.remove(0);
			return "" + candidate;
		}

		return "";
	}

	State rexp2tail(List<Character> text, State previous) {
		if (eat(text, '*')) {
			return star(previous);
		}

		if (eat(text, '+')) {
			State duplicate = duplicate(previous);
			State dupEnd = findAccepting(duplicate);
			recursivelySetNotAccepting(duplicate);

			State star = star(previous);
			dupEnd.addTransition(star);

			return duplicate;
		}

		return previous;
	}

	private State star(State previous) {
		State start = new State();
		State end = new State(true);

		start.addTransition(end);
		end.addTransition(start);

		State copy = duplicate(previous);
		State oldEnd = findAccepting(copy);
		recursivelySetNotAccepting(copy);

		start.addTransition(copy);
		oldEnd.addTransition(end);

		return start;
	}

	State rexp3(List<Character> text, State previous) {
		CharacterClass cc = charClass(text);

		if (cc == null) {
			return new State(true);
		}

		State copy = duplicate(previous);
		State copyEnd = findAccepting(copy);
		recursivelySetNotAccepting(copy);
		copyEnd.addTransition(new Transition(new State(true), cc.getIncluded()));

		return copy;
	}

	CharacterClass charClass(List<Character> text) {
		if (eat(text, '.')) {
			return new CharacterClass(PRINTABLE_START, PRINTABLE_END);
		}

		if (eat(text, '[')) {
			return charClass1(text, new CharacterClass());
		}

		if (eat(text, '$')) {
			return getDefinedClass(text);
		}

		return null;
	}

	private CharacterClass getDefinedClass(List<Character> text) {
		StringBuilder builder = new StringBuilder();

		for (int i = 0; i < text.size() && i < longestClassLength; i++) {
			builder.append(text.get(i));
			
			if (classes.containsKey(builder.toString())) {
				break;
			}
		}

		String key = builder.toString();
		CharacterClass cc = classes.get(key);

		if (cc != null) {
			for (int i = 0; i < key.length(); i++) {
				text.remove(0);
			}
		}

		return cc;
	}

	CharacterClass charClass1(List<Character> text, CharacterClass previous) {
		CharacterClass list = charSetList(text, new CharacterClass());

		if (list != null) {
			return list;
		}

		return excludeSet(text);
	}

	CharacterClass charSetList(List<Character> text, CharacterClass previous) {
		if (eat(text, ']')) {
			return previous;
		}

		CharacterClass set = charSet(text);

		if (set == null) {
			return null;
		}

		set.include(previous);
		CharacterClass list = charSetList(text, set);

		return list;
	}

	CharacterClass charSet(List<Character> text) {
		String sequence = eatCLSChar(text);

		if (sequence.isEmpty()) {
			return null;
		}

		CharacterClass tail = charSetTail(text);

		for (char c : sequence.toCharArray()) {
			tail.include(c);
		}

		return tail;
	}

	static String eatCLSChar(List<Character> text) {
		if (text.size() == 0) {
			return "";
		}

		char candidate = text.get(0);

		// Escape sequence
		if (candidate == '\\') {
			if (text.size() == 1) {
				return "";
			}

			if (CLS_SPECIAL.contains(text.get(1))) {
				text.remove(0);
				return "" + text.remove(0);
			}
		}

		// Printable character (less space)
		if (candidate >= PRINTABLE_START && candidate <= PRINTABLE_END) {
			if (CLS_SPECIAL.contains(candidate)) {
				return "";
			}

			text.remove(0);

			if (!text.isEmpty() && text.get(0) == '-') {
				if (text.size() >= 2) {
					char end = text.get(1);
					StringBuilder builder = new StringBuilder();

					for (char c = candidate; c <= end; c++) {
						builder.append(c);
					}

					text.remove(0);
					text.remove(0);
					return builder.toString();
				}
			}

			return "" + candidate;
		}

		return "";
	}

	CharacterClass charSetTail(List<Character> text) {
		String sequence = eatCLSChar(text);

		if (sequence.isEmpty()) {
			return new CharacterClass();
		} else {
			CharacterClass cc = new CharacterClass();

			for (char c : sequence.toCharArray()) {
				cc.include(c);
			}

			return cc;
		}
	}

	CharacterClass excludeSet(List<Character> text) {
		List<Character> copy = new LinkedList<>(text);

		if (!eat(copy, '^')) {
			return null;
		}

		CharacterClass toExclude = charSetList(copy, new CharacterClass());

		if (toExclude == null) {
			return null;
		}

		if (!eat(copy, 'I')) {
			return null;
		}

		if (!eat(copy, 'N')) {
			return null;
		}

		CharacterClass from = new CharacterClass(excludeSetTail(copy));
		from.exclude(toExclude);

		text.clear();
		text.addAll(copy);

		return from;
	}

	CharacterClass excludeSetTail(List<Character> text) {
		if (eat(text, '[')) {
			return charSetList(text, new CharacterClass());
		}

		if (!eat(text, '$')) {
			return null;
		}

		return getDefinedClass(text);
	}

	static State findAccepting(State start) {
		return findAccepting(start, new HashSet<State>());
	}

	private static State findAccepting(State start, Set<State> visited) {
		if (start.isAccepting()) {
			return start;
		}

		if (visited.contains(start)) {
			return null;
		}

		visited.add(start);

		for (Transition t : start.getTransitions()) {
			State accepting = findAccepting(t.getEnd(), visited);

			if (accepting != null) {
				return accepting;
			}
		}

		return null;
	}

	static void recursivelySetNotAccepting(State start) {
		recursivelySetNotAccepting(start, new HashSet<State>());
	}

	private static void recursivelySetNotAccepting(State state,
			Set<State> visited) {
		// Just in case...
		if (state == null) {
			return;
		}

		if (visited.contains(state)) {
			return;
		}

		state.setAccepting(false);
		visited.add(state);

		for (Transition t : state.getTransitions()) {
			recursivelySetNotAccepting(t.getEnd(), visited);
		}
	}

	private boolean eat(List<Character> text, char c) {
		if (text.size() > 0 && text.get(0) == c) {
			text.remove(0);
			return true;
		}

		return false;
	}

	static State duplicate(State start) {
		Map<State, State> visited = new HashMap<>();
		return duplicate(start, visited);
	}

	private static State duplicate(State current, Map<State, State> visited) {
		if (visited.containsKey(current)) {
			return visited.get(current);
		}

		State copy = new State(current);
		visited.put(current, copy);

		for (Transition t : copy.getTransitions()) {
			State oldEnd = t.getEnd();
			State newEnd = duplicate(oldEnd, visited);
			t.setEnd(newEnd);
		}

		return copy;
	}

	public String getLastKey() {
		return lastKey;
	}

	public State getLastNFA() {
		return lastNFA;
	}

	public CharacterClass getLastCC() {
		return lastCC;
	}
}
